1. State of the Art
The invention relates to a method and apparatus to segment-wise detect and bring into coincidence signal waveforms which can be converted into monotone and continuous trajectories, in particular for purposes of real-time pattern recognition, of position finding and determination of transit-time differentials. Said signals are sample in time-discrete manner at the input side, are detected by correlation and thereupon the signal transit-times of different pairs of signal combinations and of different signal waveforms will then be determined.
The invention also relates to apparatus implementing such a method.
A procedure of the above kind used in signal detection is based on conventional template matching wherein the input signal is correlated with a pre-stored reference signal. By means of time-discrete sampling, the signal is rendered as a sequence of input vectors which form a matrix within which the signal is determined by the sum of all matrix pixel positions. In this matrix, correlation is determined by counting the coincident pixel positions between the input and the reference signal. This procedure is modified in time-sequence template matching in that an input vector is correlated with the search vector in each clock step and the partial results are stored in a memory and are summed after n clock steps into a total correlation result.
Time-sequence template matching is expanded into a parallel multi-template procedure with n search patterns by replicating the correlation unit n-fold and by mounting n correlation units next to each other. The input vectors pass through the correlation units and the correlation of an input vector with the comparison vector is carried out in each correlation unit.
A translationally invariant parallel, multi-template matching procedure is known from xe2x80x9cLazzaro, J. and Mead, C, xe2x80x98A silicon model of auditory localizationxe2x80x99 (1989), Neural computation, 1, pp 47-57xe2x80x9d. Therein the transit-time differential of acoustic signals is determined in two coupled functional units, namely an analog silicon cochlea which simulates the properties of a cochlea in biological systems and a subsequent correlation unit. At the input side, the silicon cochlea receives signals which drive the silicon cochlea into an energized state. Depending on the drive signal, sensors mounted equidistantly along the cochlea are actuated which relay the standard pulses to the subsequent correlation unit. This apparatus operates pairwise and the standard pulses received from the right or left cochlea pass through an antiparallel correlation unit consisting of two sets of antiparallel delay lines, each pair of delay lines being combined at the same sensor position. AND gates are mounted equidistantly along the delay lines and sample the signal status of the delay lines and, in the event of coincidence caused by standard pulses simultaneously incident on the AND gate, generate a coincidence signal at the gate output. The correlation unit determines the coincidences of the standard pulses at each pair of lines and the number of coincidences along the same positioning of the AND gates in the direction of the delay lines is counted. The output is a vector of signal-transit differentials per clock step. Accordingly the known procedure is based on simulating a cochlea and determining coincidences along analog delay lines.
Furthermore U.S. Pat. No. 5,417,113 discloses a procedure allowing to localize sound sources by means of test data from several silicon cochlea. The microphone signals are fed pair-wise to several silicon cochlea carrying out a 2-D correlation along predetermined delay lines. The detected coincidences are fed from the particular silicon cochlea to a subsequent 3D analyzer which, upon comparing the characteristic signatures of the 2D output data, results in improved localization of the sound source.
2. Drawbacks of the State of the Art
The conventional template-matching procedures incur the drawback that they fail to be invariant in the presence of spatial shifts. Only a signal sequence present at the same time of synchronization at which the correlation between input and comparison vector is started will result in maximum correlation. If the correlation between the input and the comparison vector is shifted by one or more sequences, the image and search patterns no longer coincide.
The known translationally invariant, parallel, multi-template matching procedures used to determine the transit-time differential of acoustic signals incur the drawback of the complex simulation of a biological cochlea, in particular in tuning the response of the cochlea to different energizing signals by varying the relevant parameters describing the cochlea.
Another drawback resulting from the circuitry of the heretofore designed analog configurations is the adjustment, subject to manufacturing tolerances, of the delay speeds in the analog delay lines subject.
The heretofore predominantly employed digital signal processors (DSP""s) incur a drawback in that they do not properly match the present problem""s solution contained in the method and apparatus of the invention. A DSP is incapable of solving said problem of a defined magnitude within an adequately short time, and in many cases such inability may entail problems.
A further general drawback of the DSP""s prevailingly used to-date for signal processing and pattern recognition is that the procedure and the apparatus poorly match the above solution to the problem addressed herein. A DSP is incapable of solving such a problem of a defined magnitude at the same time as the method and apparatus herein disclosed. The DSP architecture cannot process the signal flows in the manner of the method and apparatus of the invention.
Another general drawback of the DSP""s is the central control unit and the scarcity of computers able to process the data flows in the manner of the method and apparatus of the present invention. As regards digital signal processors, instructions are stored in the computers, operands are retrieved, and results are filed in registers. Because of its fixed CPU architecture, a digital signal processor is unable to simulate the apparatus""signal-flow architecture at which the signal flows pass in time though said apparatus.
The objective of the invention is to create a method and apparatus to segment-wise detect and bring into coincidence signal waveforms which can be converted into monotone and continuous trajectories, in particular to recognize patterns in real time, to localize and to monitor optical and acoustic signals, and to determine transit differentials with increased accuracy of measurement by making it possible to program the key waveforms and the resolution.
Another objective of the invention is to accelerate calculations in order to include several domains of application of real-time pattern recognition.
In the method of the invention, first pattern recognition is carried out and then the determination of the transit-time differential by detecting key waveforms, and the information is processed further in a subsequent multi-coincidence unit; shift-invariant, parallel multi-template matching is carried out during which key waveforms are correlated in parallel and an output per clock step, illustratively of a set of transit-time differentials, is created in the said subsequent multi-coincidence unit.
The method to segment-wise determine pattern recognition and transit-time differentials of signal waveforms which can be converted into monotone and continuous space-time trajectories, in particular for purposes of real-time pattern recognition, is characterized in that pre-programmed key signals are detected by signal sampling and processing the sampled data, further by subjecting to multiple coincidences combined signal pairs of different signal transit times and different waveforms. At the input side the signals are sampled in a sequence of input vectors, each input vector consecutively passing through a signal detection unit consisting of parallel, programmable signal-flow paths, a maximum correlation result being achieved in said signal detection unit wherein, by programming the speed of propagation in the signal flow paths, a key signal shall produce, at a given position along the signal flow path by summing all partial results at correlation units orthogonal thereto and mounted at the individual signal nodes, so that, by comparing the correlation result with a programmable threshold value and exceeding this threshold value a detection signal shall be generated, the detection signals from all correlation units subsequently passing through a multi-coincidence unit consisting in each case of pairwise, antiparallel delay lines, and where the impact of two mutually opposite detection signals by means of equidistant configuration of coincidence elements along the delay line generates a coincidence of which the particular spatial location along the delay line encodes the presence of a given transit-time differential of a signal of a particular waveform.
The apparatus implementing the method of the invention is characterized in that signals are sampled at a receiver and are converted into a sequence of input vectors which are processed consecutively in a signal detection unit consisting of programmable chains of signal flows and of adders-comparators mounted orthogonally thereto at equidistant spacings and detecting the particular signal state of the signal flow chains at a given position in this signal flow chain, detection of a signal of a given waveform being implemented by comparing a predetermined threshold value with the correlation resultxe2x80x94 per clock stepxe2x80x94 of the related adder/comparator unit, and a standard pulse being generated when the threshold value is exceeded, the sampled standard pulses from all adder/comparator units passing through a multi-coincidence unit consisting of two antiparallel channels of sequential shift registers (antiparallel flip-flop channels), the memory flipflop chains of the adder-comparator units coding the same signal being pairwise combined by connecting each pair of memory flipflops with an AND gate along the memory flipflop chains and the coincidence of two mutually opposite standard pulses at the AND gate output triggering a timed standard pulse which by means of the given timing and the particular spatial position of the AND gate along the memory flipflop chain encodes the presence of a specific transit-time differential of a signal of a given waveform.
The essential advantages of the method of the invention applied to acoustic pattern recognition and determination of transit-time differentials are that the complex simulation of a silicon cochlea is eliminated. This silicon cochlea is replaced by a signal detection unit of which the time-response to the applied input signal and the selected set of parameters can be specified deterministically in accurate manner.
Another advantage in all pattern-recognition procedures is the programmability of the signal detection unit, whereby programming the signal speeds in the signal flow chains of propagation allows programming the detection of sets of given key signal waveforms. A further advantage is that the resolution of the transit-time differentials following pattern recognition can be varied by fixing the interval of the maximally registrable transit-time differential. Yet another advantage of the method of the invention is that by means of synchronous timing, the speeds of propagation of all signal flow chains can be matched accurately to each other. Another advantage is adaptation to the problem by programming the resolution, thereby attaining higher accuracy of measurement of key signals, as a result of which, by means of the method of the invention, the distance of a signal source from the receiver can be determined at high resolution, also, that by means of said method, the azimuth of a signal source in the receiver plane relative to the receiver can be determined at high accuracy, and again, that by means of the method of the invention, voice and image signals can be detected with high resolution.
The aforementioned advantages of in creased resolution and ability to match special applications obviously also cover other applications of this method. In many physical cases an object moves through a phase space in a characteristic trajectory. Such a path can be detected by the method and apparatus of the invention, Because the said method and apparatus are trajectory-detecting, knowing physical particulars of the phase space, it will be possible to determine an object""s relevant parameters such as spatial position, angular position, distance, speed, acceleration etc. Accordingly the applications also include in particular measuring speed and acceleration, compensating deviations from the rest position, tactile pattern recognition, etc.
Because the working time is much less than for the DSP""s, the method and apparatus of the invention also are advantageous when monitoring the safety of rapidly evolving processes, for instance relating to aircraft or reactor safety, further in monitoring industrial production facilities or patients in medical care.
The method and apparatus of the invention however are not applicable to such waveforms that cannot be converted into segmented, monotone and continuous trajectories or time series.
An advantage of the application of the invention to circuitry is that conventional electronic circuits may be used and in that the circuit architecture is highly structured. Where needed it may be converted into a regular VLSI chip design because the circuit consists only of three basic elements which when connected form an elementary basic functional unit which might be construed as a basic cell. The VLSI chip is formed by n-fold replication and overlayering and subsequent simple connection of the cells.
The solution of the method of the invention is characterized by the features of claims 1 through 8 and the related circuitry solution of the invention is determined by the features of claims 9 thorough 17.
The further claims 18 through 41 relate to technical fields and equipment which may employ the method and apparatus of the invention.
Further features and advantages of the invention are discussed below in relation to the implementations shown in the drawings.